Today, there are many applications that require fair access to information or processing services provided by an application. Fair access implies that no user has preferential access to the information or services in the database. A level playing field is created for all users.
As an example, fair access might be defined by the requirement that the time to query or to update database information is the same for all users, regardless of their location. For instance, a stock market trading system must provide, often by regulation, the same access time to market information and to the market's trading functions for all users. Otherwise, users with faster access will have a marked advantage over those with slower access. This is especially important when computers rather than people are doing the trading because of the computer's extremely fast decision times.
Fair access is defined by a fairness criteria policy. This policy may simply state that all users are to be provided the same access. Alternatively, it may require that some users be given priority over other users in that high-priority users are guaranteed faster access to data than other users. Still another policy may require that each user have access to data changes after some fixed time delay specified for that user. The fairness criteria might be predetermined, or it could be dynamic, changing under certain conditions or as business rules dictate.
Unless special measures are taken, user access is impacted by communication delays in the network connecting the user to the data-processing system. Application-processing delays or other system delays may also play a role. Round-trip communication delays from when a request is made to when a reply is received typically range from almost zero to hundreds of milliseconds, depending upon the distance of the user from the data processing site, upon the data processing time, and upon the nature of the communication channels and equipment connecting the user to that site. Communication delays are dynamic. They can vary as network or load conditions vary. Any fairness methodology must compensate for these variations to meet the fairness criteria.
1. Global Access to Information
Today's communication and data processing technologies allow users around the world to access a common online database so that they can all participate in a common application. An online database is one that is accessible in real time by external entities over a communication network. Online databases are typically, but not necessarily, stored on persistent storage such as disk. However, an online database might be stored in volatile memory for performance purposes. An example of the use of online database technologies is an online retail store such as Amazon.com. A user anywhere in the world can browse Amazon's inventory of goods and can purchase those items via credit card or via an intermediate payer such as PayPal®.
Users connect to remote database servers via communication channels, which are typically provided by common carriers. Much of today's communication is done over the Internet, which provides reasonably reliable and low-cost communication channels to users working at their PC or workstation browsers. In addition, there are many other types of communication channels in use, both over public networks and over private networks.
Communication between a user and a remote data-processing center is accomplished by exchanging messages. In a typical interaction, a user sends a message to a remote server requesting some service. The server then responds with a message providing the requested information or confirming the completion of the requested action (FIG. 1).
The time that it takes to pass a message between a user and a server is called the “propagation delay” and is limited by the speed of light. It takes light about five milliseconds to travel 1,000 miles in a vacuum. In fiber or copper wire, it takes about twice as long, or about 10 milliseconds per 1,000 miles. Thus, a message traveling from London, England, to Sydney, Australia—about 12,000 miles apart, will take about 120 milliseconds over fiber or copper cable. This propagation delay is magnified even further by delays through repeaters and through other electronic equipment used in the channel to enhance signal quality. Furthermore, most interactions comprise a request followed by a response and entail a round trip over the communication channel. In this case, the round-trip time between London and Sydney may be 240 milliseconds or more.
2. Fair Access to Information
In many applications, such propagation delays are immaterial. If a user at a browser is expecting a response in two or three seconds, a few hundred extra milliseconds may not be noticeable. In these systems, as soon as the data is received by a system, it is available to the system's users. However, in some applications, users are competing with each other, and thus the propagation delays may be very important. More to the point, if one user is close to the database and has much faster access than a user remote from the database, the user that is closer may have an advantage referred to herein as an “unfair advantage.”
An example of this problem is an auction market. In such markets, an item of some sort is put up for sale. Bidders then compete with each other for the item. The highest price wins the auction. Similarly, an item might be requested and bidders compete to sell that item to the requester at the lowest price that they are willing to sell it. If some bidders have very fast (say millisecond) access to the market, they are in a much better position to bid than are others with much slower access (say seconds). In such a case, this is an unfair market. It gives an advantage to certain bidders over others.
Contemporary examples of auction markets are Internet auction sites such as eBay®, in which a wide variety of objects are put up for sale. These markets are generally manual in that competing bidders are interfacing to the market via their keyboards. Those with faster access can bid more quickly than those with slower access, thereby leading to an unfair advantage.
A more critical case is that of computer trading. If computers are monitoring the market and are automatically making bids, trading activity occurs at a much higher rate—perhaps significantly faster than the differences in access times. Differences measured in milliseconds can be critical. Differences measured in hundreds of milliseconds can make the market untenable. An example of computer trading is a stock market. In this case, a few millisecond advantage can have a tremendous financial value to the lucky trader.
FIG. 2 illustrates an example in which traders are trading on two different stock exchanges located thousands of miles apart. Consider two hypothetical stock exchanges—one in London, England, and one in Sydney, Australia—each with a local trading system that allows traders to obtain price quotations and to execute trades against a local database containing the market data for that exchange. To get price quotations and to execute trades on the London-based stock exchange, traders in London will have very fast access to the market data—typically in the order of a few milliseconds (1). However, using the London/Sydney round-trip signal propagation time developed above, it can take on the order of 240 milliseconds or more for a trader in Australia to make a trade on the London-based exchange (2). The reverse holds true for executions (3) and (4) against the Australian-based market. In either case, traders using their local exchange have an unfair advantage over those traders who are remotely located. Many markets would consider this is an unfair system. The differences in access times to the application database for different users can be orders of magnitude apart, depending upon where the users are located.
As a consequence, many stock exchanges are affected by regulations that govern the allowable differences in access times across the trading community. All traders must suffer substantially the same delay. If one community of traders has an access time to the system of 240 milliseconds, then all traders must suffer this access time no matter where they are located. These systems must provide fair access to all of the information distributed across the network to all users.
This is only one example of an application in which fairness criteria may be imposed. Any application that pits one user or group against others is a candidate for enforcing fairness. The fairness requirement extends from auction markets of various forms to many other applications, such as online games.
3. Determining Propagation Time
In order to achieve a fair system, it is necessary to be able to measure the propagation delays between two or more systems. Propagation delays may be caused by delays through the communication channel or by delays in the application. If the systems are geographically separated, communication delays will generally be predominant as they will be measured in milliseconds as compared to microseconds for application delays. However, if systems are collocated, application delays may predominate. Communication propagation delay may be measured in several ways using currently known methodologies, as described next.
a. Accurate Clocks
If all systems in the network use accurate clocks, then it is only necessary for one system to send a timestamped message to a second system. The second system notes the time of receipt of the message and calculates the communication propagation delay by subtracting the time that the message was sent from the current time. Likewise, the original system can determine the channel propagation delay between it and the second system from a timestamped message sent to it by the second system. In this way, each system in the network can determine the propagation time to it from every other system in the network. Systems may then exchange these propagation delays so that all systems know the propagation time along any path in the network. In order to be accurate, a clock must be initially set properly, and it must not drift. Accurate time sources include atomic clocks, radio broadcasts (such as from WWV or WWVB in Colorado), Loran, and GPS.
b. Synchronized Clocks
The systems may use software synchronization techniques to keep all of their clocks synchronized with each other and, optionally, synchronized with an accurate clock (or with the average time of several accurate clocks). A common software synchronization technique in use today is the Network Time Protocol, or NTP. Via timestamped messages exchanged between systems, NTP can determine how far apart their clocks are from each other. It then can speed up or slow down the clock of one system to synchronize it with another. NTP organizes systems into a hierarchical tree, where each level of the tree is known as a stratum. Stratum 0 systems have accurate clocks. Stratum 1 systems synchronize with Stratum 0 systems, Stratum 2 systems synchronize with Stratum 1 systems, and so on. The further down the chain a system is, the less accurate the system's clock. However, NTP synchronization error is generally measured as a few milliseconds.
If there is no Stratum 0 system in the network, the systems are time-synchronized with each other but not with real civil time. However, they can each still interact with each other on the same relative time scale.
c. Unsynchronized Clocks
In many geographically distributed systems, the system clocks are not synchronized with each other. There may be inter-clock divergences of many seconds or more. However, in this case, the round-trip channel propagation may still be accurately determined by using the procedure used by NTP. See NTP RFC 1305, http://WorldWideWeb.eecis.udel.edu/˜mills/database/rfc/rfc1305.
Referring to FIG. 3, System 1 sends a message with its current timestamp, T1, to System 2. Upon receipt, System 2 timestamps the message with timestamp T2. It then returns the message to System 1 with a timestamp, T3, of the time of its transmission. System 1 notes the time, T4, that it receives the returned message from System 1.
It is now known that it took T4−T1 seconds for the message to travel from System 1 to System 2 and back to System 1. Furthermore, System 2 held the message for a time of T3−T2 seconds. Therefore, the round-trip time attributable to communications isround-trip time=(T4−T1)−(T3−T2)Assuming that the communication channel is symmetric—that is, that the communication propagation delays are the same in each direction, thenchannel propagation time=(round-trip time)/2This procedure results in accurate round-trip times even if the System 1 and System 2 clocks are not closely synchronized. However, this procedure has several sources of error, which can be corrected to a large extent:Channel Asymmetry—The calculation of channel propagation time from the round-trip time assumes that the channel is symmetric. That is, the communication delay in each direction is the same. This condition can be met by ensuring that the communication channels in each direction are configured the same. The channels in each direction should use the same common carrier or private services, and the communication channel distance should be the same in both directions.
Variable Propagation Time—In some networks, and especially over the Internet, the channel propagation delay can vary over time. This can be caused by changes in routing through the network or by network congestion. In these cases, the channel propagation time should be measured periodically (typically every few minutes). Alternatively, the channel propagation time could be measured at the initiation of each change sequence (a transaction) or upon each connection made between the systems over the communication channel. Rather than simply accepting the last measurement, the average of the last few measurements can be used to filter out transient changes in the propagation delay.
d. Collocated Systems
If two or more systems are collocated, the communication propagation delay between them may be negligible; and delays within the application may become predominant. Application delays can be measured by routing the timing message described above through the application. The receipt of the system of the timing message and its retransmission are still noted by the timestamps T2 and T3. However, the time from T2 to T3 now includes the application time.
This same procedure can be used when the communication and application delays are comparable, as it will give a round-trip time that includes both communication delays and application delays.
4. Differential Delay
There are several prior art system and network architectures that can be used to ensure fairness. All utilize techniques that delay information access to the lowest common denominator. That is, all users must experience the same delays in obtaining access to the application data. Users who have fast access must have that access slowed to the access time of the user with the slowest access.
In the case of a single server (FIG. 4), this is done by measuring the propagation delay from the server to each client system (that is, the user's system) as described above with reference to FIG. 3. Then a differential delay is calculated for each client. A client's differential delay is the maximum client delay of all clients in the network minus the client's own delay:Differential delay for a client=maximum client propagation delay−this client's propagation delay.
The differential delay for a client is the amount of time that must be inserted into a client's request path and response path so that the time for the server to receive a request from any client is the same and so that the time for each client to receive a response from the server is the same.
For instance, if there are three clients, and if the propagation delay from each client to the server is as shown in the following table, the differential delays are those shown. In this case, the client with the longest propagation delay is Client 2 with a delay of 120 milliseconds. Since Client 1 only has a 30 millisecond propagation delay, its requests and its responses must be delayed by 90 milliseconds before being processed or delivered in order to provide fair access relative to Client 2. 90 milliseconds is Client 1's differential delay. Likewise, Client 3 has a differential delay of 40 milliseconds.
PropagationDelayDifferential(msec.)Delay (msec.)Client 13090Client 21200Client 38040If there are multiple nodes and database copies in the network, as shown in FIG. 5, then the servers must calculate not only the differential delays between themselves and their clients, but also between each other. This more complicated case is discussed later.
a. Client Monitoring
Perhaps the simplest network architecture to be considered is that of a single database that is accessed by a single server supporting users spread over a large geographic range. As simple as this architecture is to describe, the application of fairness to it is not so simple.
FIG. 6 shows such a network architecture with a system located in New York. A community of one or more users is located locally in New York, and others are located remotely in London and in Shanghai. Clearly, the local users in New York will probably have faster access to data and services than those in London and Shanghai. Furthermore, London users are likely to have faster access than Shanghai users. In this architecture, fairness can be achieved by shifting the responsibility for fairness to the user terminals (or computers, if the “users” are, in fact, computers). Collectively, they can be called endpoints clients. Clients request services of the central server.
The first step, as shown in FIG. 7, is for the server to measure the channel propagation delays to each of its clients. It then calculates the differential delay for each client and sends this value to each client. It may do this periodically, and it may average several measurements to arrive at the current propagation delays.
Each client receives from the server its differential delay time by which it must delay its requests and responses. The client delays the transmission of all of its requests to the server by the differential delay time. When a response is received to a request, the client will delay the processing of that response by the differential delay. In this way, all clients will suffer the same delay in getting a request to the server and will then suffer the same delay in receiving the response from the server.
Alternatively, the server could measure the client channel propagation times and send only the maximum propagation time to all clients. Each client would then measure its own propagation time and calculate its own differential delay.
Using this latter algorithm as an example, as shown in FIG. 6, assume that New York clients measure a propagation delay of ten milliseconds, that London clients measure a propagation delay of 60 milliseconds, and that Shanghai clients measure a propagation delay of 200 milliseconds. Upon receiving these delay time reports, the server will send a 200 msec. maximum delay directive to all clients. Consequently:                i. The New York clients will calculate a differential delay of 190 milliseconds. They will delay all requests by 190 milliseconds, leading to a delay time for requests received at the server of 200 msec. Responses from the server will likewise be delayed by 190 milliseconds, leading to a response delay time of 200 msec.        ii. The London clients will calculate a differential delay of 140 milliseconds. They will delay all requests by 140 milliseconds, leading to a delay time for requests received at the server of 200 msec. Responses from the server will likewise be delayed by 140 milliseconds, leading to a response delay time of 200 msec.        iii. The Shanghai clients will calculate a differential delay of zero milliseconds. Therefore, it will take approximately 200 msec. for their requests to arrive at the server and another 200 msec. for them to receive the replies.Since all clients experience the same delay (in this case, 200 msec. in each direction), the system is fair.        
b. Server Monitoring
Alternatively, as shown in FIG. 8, the same result can be obtained by having the server delay all requests and responses from and to a given client by the calculated differential delay, thus relieving the clients of having to make this adjustment.
c. Read-only Locality—Tightly Clustered Users
If fairness is enforced via client or server monitoring, a single server node system imposes the maximum transaction response time on all clients in the system for queries, services, and updates. This penalty can be relaxed by providing additional local servers with a read-only copy of the database close to each community of users. One of the servers is designated as the master node, at which all updates are made. The other servers can be considered slave nodes.
Changes made to the database as a result of updates to the master node are replicated in real time to all of the slave nodes with appropriate fairness delays, where they are applied to the local database copies and are available to the local community of users. These users can read data very quickly (such as getting a stock quote) since the data is local to them, but they must communicate over the network in order to effect a database update (such as executing a trade).
For instance, FIG. 9 shows the single-node system of FIG. 6 expanded to accommodate local nodes in London and Shanghai. The New York node is the master node. There are slave nodes located in Shanghai and in London. If a client in Shanghai or London needs to update the database, its server sends that update to the New York server (1). The New York server will update its database (2) and will then replicate the database changes to Shanghai and London (3).
Provided that all clients are collocated with their nodes (that is, they form tight clusters) so that their propagation times can be ignored, the result is that all clients have fair read-only access to application data that already has been published. Their only reading delays are that of sending read requests to their local servers and of receiving the responses from those servers. Information access will be substantially the same for all clients.
However, unless special steps are taken, the execution of requests requiring database updates may not be fair. New York clients have direct access to the master database for updates, whereas London and Shanghai clients must send update requests across the network. Therefore, updates will reach the New York database before they reach the London or Shanghai databases. Consequently, New York users will see newly published data before their peers in London or Shanghai.
This problem can be solved by having the servers monitor communication delays between each other in a manner analogous to the client monitoring technique described earlier. In this case, the servers impose differential delays on update requests and responses so that all update requests and responses are delayed by the same amount of time from when they were made. In this way, it is ensured that data updates are published fairly.
Using this method, each remote slave server monitors the communication delay between it and the master server. Periodically, the slave servers report their measured delays to the master, which will broadcast the largest such delay to all slave servers. Each slave server, as well as the master server, will calculate its own differential delay based on the maximum delay and will delay its requests and its responses (or the processing of each) by the differential delay, as described previously. In this way, all requests are received and processed by the master server fairly, and all responses are published fairly.
Alternatively, the master server can monitor the communication delays between itself and each of the slave servers. It will then delay each request from a specific slave and each of its responses to that slave by the differential delay time between it and that slave. It will also delay its own requests and responses by its differential delay (which will be equal to the largest propagation time from itself to any of the slave servers).
Since all clients have local read-only access to the information in the database, they can all read information which is already in the database with substantially the same delays. This is fair read access. Also, all updates will be made visible at all nodes at the same time so that fair access to changed (manipulated) data is provided. The result is a fair system.
d. Read-only Locality—Loosely Clustered Users
Client monitoring can be extended in this architecture to provide fairness to clients that are not local to a node. Consider a case in which several slave nodes provide database access services to communities of clients but in which the clients are geographically dispersed and are at different distances from their serving nodes. Even though the nodes may be issuing requests and receiving responses fairly, this does not mean that all clients are being treated fairly since some of them may be at a greater distance from their serving nodes than other clients.
This situation can again be corrected via client monitoring, as described earlier. In addition to the slave nodes monitoring communication delays to the master node (or the master node measuring these delays), each client will also monitor communication delays to its serving node and will report these delays to its node (or the serving node can calculate this delay with its clients). When a slave node reports communication delays to the master node, it will report not only its communication delay but also the maximum communication delay measured by its own clients.
As before, the master node will broadcast the maximum nodal communication delay to all nodes. Each node will calculate its own differential communication delay, which it will use to delay requests and responses between itself and the master node for fairness. In addition, the master node will also broadcast to the slave nodes the maximum overall delay separating a client from its serving node.
Each node, including the master node, will send to its clients the maximum client/server delay in the entire network. The clients will use this information to calculate an additional differential delay that they will use to further delay requests and responses. This differential delay will be the difference between the maximum client/server delay and its own delay to its server. Alternatively, the slave nodes can impose these delays in their own processing so that the clients are not involved in the process.
For instance, with respect to FIG. 9, assume that the communication propagation delays between the slave nodes and the master New York node are as shown in FIG. 6—60 msec. for the London node and 200 msec. for the Shanghai node. Furthermore, assume that the furthest client is a Chinese client that is another 100 msec. from the Shanghai node.
The master node, as described above, will broadcast a maximum nodal delay of 200 msec. and a maximum client delay of 100 msec. to all slave nodes. The nodes will add differential delays based on the maximum nodal delay, discussed earlier, to all requests and responses. For instance, the London node will delay its requests and responses by 140 msec., as described above (200−60).
Consider a client that is served by the London node. This client must ensure that it imposes an additional 100 msec. delay on each request and on each response to match that of the furthest Chinese node. If the London client has a 10 msec. delay in its connection to the London node, the client must impose an additional 90 msec. delay on its requests and responses.
Alternatively, these delays could be calculated and imposed by the slave nodes. Nodal calculations of delays may be a more secure way to achieve fairness in that it precludes fraudulent calculations by clients to enhance their own access.
By imposing this timing condition on each client in the system, all responses and requests will be delayed by the same total amount; and information access, both query and update, is fair. In the example described above with 300 milliseconds of total delay time, with respect to the London client, there will be a 60 msec. delay from the New York server to the London server, a 140 msec. delay inserted by the London server, a 10 msec. delay from the London server to the client, and a 90 msec. delay inserted by the client, yielding a total delay of 300 msec.
State-of-the-art methods work fine for single databases. What is needed are methods that work for multiple databases or that are more efficient for single databases.